/*
 * =====================================================================================
 *
 *       Filename:  sort_list.c
 *
 *    Description:  sort linked list by merging ordered sub lists recursively.
 *
 *        Created:  2020-07-10 14:54
 *
 *         Author:  limingle
 *          Email:  lml@xdja.com
 *   Organization:  XDJA Tech.CO.ltd.
 *
 * =====================================================================================
 */
#include <stdio.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

typedef struct ListNode ListNode;

ListNode * next_unordered_list(ListNode *);

ListNode * merge_sort(ListNode *, ListNode *);

struct ListNode * sortList(ListNode * head){
    ListNode *next = next_unordered_list(head);
    if (next == NULL)
    {
        return head;
    }
    else
    {
        return merge_sort(head, sortList(next));
    }
}

ListNode * next_unordered_list(ListNode *head)
{
    ListNode *next = head;

    while (head != NULL && head->next != NULL && head->val <= head->next->val)
    {
        head = head->next;
    }

    if (head != NULL)
    {
        next = head->next;
        head->next = NULL;
    }

    return next;
}

ListNode * merge_sort(ListNode * first, ListNode * second)
{
    if (first == NULL)
    {
        return second;
    }
    else if (second == NULL)
    {
        return first;
    }

    if (first->val > second->val)
    {
        return merge_sort(second, first);
    }
    else
    {
        ListNode ** curr = &first;
        while (*curr != NULL && (*curr)->val <= second->val)
        {
            curr = &(*curr)->next;
        }

        *curr = merge_sort(second, *curr);
        return first;
    }
}

void _print_list(ListNode *list, const char *predix)
{
    if (list != NULL)
    {
        printf("%s%d", predix, list->val);
        _print_list(list->next, "->");
    }
    else
    {
        printf("\n");
    }
}

void print_list(ListNode *list)
{
    _print_list(list, "");
}

int main(int argc, const char *argv[])
{
    ListNode a = {3, NULL};
    ListNode b = {2, NULL};
    ListNode c = {9, NULL};
    ListNode d = {5, NULL};
    ListNode e = {4, NULL};
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;

    print_list(&a);
    print_list(sortList(&a));

    return 0;
}
